import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        // 1 接收输入
        int t = in.nextInt();

        // 2 每组测试数据调用
        for(int i = 0; i < t; i++) {
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] arr = new int[n][2];
            for(int j = 0; j < n; j++) {
                arr[j][0] = in.nextInt();
                arr[j][1] = in.nextInt();
            }
            // -调用执行方法
            function(n, m, arr);
        }
    }

    public static void function(int n, int m, int[][] arr) {
        /**
         * 完全背包-求在体积小于等于m时，所能带走的最大物品价值
         * 状态表示：
         *  dp[i][j]表示在前i个物品中挑选（每个物品可多次挑选），总体积不超过j，此时的最大价值
         * 状态转移方程：
         *  不选当前的最大值 和 选择后的最大值
         *  需要保证：当前的j >= arr[i-1][0],即能最少选一件
         *  dp[i][j] = Math.max(dp[i][j], dp[i][j-arr[i-1][0]]+arr[i-1][1])
         * 初始化：
         *  使用虚拟位置法，多创建一行、一列，虚拟位置初始化为0
         * 填表顺序：
         *  从上到下，从左到右*/
        // 1 创建dp表
        int[][] dp = new int[n+1][m+1];

        // 2 初始化

        // 3 填表
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= arr[i-1][0]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i][j-arr[i-1][0]]+arr[i-1][1]);
                }
            }
        }

        // 4 返回值
        System.out.println(dp[n][m]);
    }
}